package may;

import java.util.Arrays;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-5-26 8:16
 * @description：
 * @modified By：
 * @version:
 */
public class May26 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/minimum-path-sum/ 最小路径和
     * create time: 2020-5-26 8:17
     * @params [grid]
     * @return int
     */
    public int minPathSum(int[][] grid) {
       int dp[][] = new int[grid.length][grid[0].length];
       //初始化
        dp[0][0] = grid[0][0];
        for (int i = 1; i < grid[0].length ; i++) {//初始化第一行
            dp[0][i] = dp[0][i-1]+grid[0][i];
        }
        for (int i = 1; i < grid.length; i++) {//初始化第一列
            dp[i][0] = dp[i-1][0]+grid[i][0];
        }
        for (int i = 1; i < dp.length; i++) {//从第二行开始 减少运算
            for (int j = 1; j < dp[0].length; j++) { //每行从第二哥开始算减少运算
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];//上面一格的路数+左边一格的路数
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/last-stone-weight-ii/ 最后一块石头的
     * create time: 2020-5-26 8:32
     * @params [stones]
     * @return int
     */
    public int lastStoneWeightII(int[] stones) {
        /* 由于石头拿走还能放回去，因此可以简单地把所有石头看作两堆
         * 假设总重量为 sum, 则问题转化为背包问题：如何使两堆石头总重量接近 sum / 2
         */
        int len = stones.length;
        /* 获取石头总重量 */
        int sum = 0;
        for (int i : stones) {
            sum += i;
        }
        /* 定义 dp[i] 重量
        上限为 i 时背包所能装载的最大石头重量 */
        int maxCapacity = sum / 2;
        int[] dp = new int[maxCapacity + 1]; //背包
        for (int i = 0; i < len; i++) {
            int curStone = stones[i];
            for (int j = maxCapacity; j >= curStone; j--) {
                dp[j] = Math.max(dp[j], dp[j - curStone] + curStone); //j的当前位置的最大可能装进去的容量
            }
        }
        return sum - 2 * dp[maxCapacity];

    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/coin-lcci/ 硬币 有多少种方法
     * 不能使用跳格子 因为6 的话跳格子其实是3种 111111 51 15 但是这个题目顺序改变其实也看成同一种
     * 先遍历硬币，保证在考虑一枚硬币的情况时，没有较大的硬币影响，这样，我们最终每种组合情况，都是以硬币的面额大小非递减组合。
     * 保证了同样的情况，调换顺序后重复计算的情况。
        比如计算到从面额1开始计算有多少每一个价格有多少种
     意思就是每回只考虑只有当前的面额的情况下会有多少种办法可以组合

   * create time: 2020-5-26 10:12
     * @params [n]
     * @return int
     */
    public int waysToChange(int n) {
        int[] dp = new int[n + 1];
        int[] coins = new int[]{1,5,10,25};
        //刚好可以用一个硬币凑成的情况，是一种情况
        // while i == coin :
        //dp[i] = dp[i - coin] => dp[0]
        dp[0] = 1;
        /**
         * dp方程：dp[i] += dp[i - coin];
         */
        for(int coin : coins) {
            for(int i = coin; i <= n; i++) {//起始位置最起码是在面值的位置上
                dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
            }
        }

        return dp[n];
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/decode-ways/ 解码方法
     * create time: 2020-5-26 15:30
     * @params [s]
     * @return int
     */
    public int numDecodings(String s) {
        char[] nums = s.toCharArray();
        int len = nums.length;
        int[] dp = new int[len+1];  // dp[i] 表示从第i+1个数到第n个数的所有方案数
        dp[len] = 1;
        // 从右往左
        for(int i = len-1; i >= 0; i--) {
            // 注意判断0字符
            if (nums[i] == '0') continue;   // 当开始位为0字符时不满足任意一个字母的解析，跳过
            int num = 0;
            for (int j = i; j < len && j-i<2; j++) {
                num = num*10 + (nums[j]-'0');
                // 对子状态dp[j+1]为0开头的也可进行添加，因为没有赋值为dp[j+1]为0
                if (num <= 26) dp[i] += dp[j+1];
            }
        }
        return dp[0];
    }
    //当前字符为0
    //极限值可以考虑优化吗
    public int numDecodings2(String s) {
        char[] nums = s.toCharArray();
        if(nums[0]=='0'){
            return 0;
        }
        int len = nums.length;
        int[] dp = new int[len+1];  // dp[i] 表示从第i+1个数到第n个数的所有方案数
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= nums.length; i++) {
            int j = i-1;
            int num = 0;
//            i-j<2是因为只要和前一个进行判断就可以
            if (nums[j] == '0') {
                if(nums[j-1]=='1'||nums[j-1]=='2'){
                    if(i==len){ //最后一个字符是0
                        dp[i] = dp[i-2];
                    }else{
                        dp[i] = dp[i-1];

                    }
                }
                continue;
            }
            dp[i] = dp[i-1];
            if(nums[j-1]!='0'){
                num = (nums[j-1]-'0')*10 + (nums[j]-'0');
                if(num<=26){//可以和前面联动组合可能性翻倍
                    if(i>1) //第二个字符 特殊处理
                        dp[i] += dp[i-2];
                }
            }
        }
        return dp[len];
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/restore-the-array/ 恢复数组
     * 边界值: 0 数字是不会出现前导是0的 所以1000 是1000 不会出现别的组合
     * 字符串是从右到左规划 里面又是以s[i]为最左端向右遍历
     * create time: 2020-5-26 16:11
     * @params [s, k]
     * @return int
     */
    public int numberOfArrays(String s, int k) {
        int m=1000000007;
        long[] dp=new long[s.length()+1];
        dp[s.length()]=1;
        for(int i=s.length()-1;i>=0;i--){
            //前导零
            if(s.charAt(i)=='0'){
                dp[i]=0;
                continue;
            }
            //解析分割出的第一个整数的值
            long parseRes=0;
            for(int j=i;j<s.length();j++){
                parseRes=parseRes*10+s.charAt(j)-'0';

                if(parseRes<=k)
                    dp[i]=(dp[i]+dp[j+1]) % m;
                    //当这个整数大于 k 时，就可以 break 了
                else
                    break;
            }
        }
        return (int)dp[0];
    }
     /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/ 剪绳子
      * 贪心算法
      * 我们首先考虑对于一段长n的绳子，我们可以切出的结果包含什么？
      *
      * 1会包含吗？ 不会，因为1 * (k - 1) < k, 只要把1和任何一个其他的片段组合在一起就有个更大的值
      * 2可以
      * 3可以
      * 4可以吗？ 它拆成两个2的效果和本身一样，因此也不考虑
      * 5以上可以吗？ 不可以，这些绳子必须拆，因为总有一种拆法比不拆更优，比如拆成 k / 2 和 k - k / 2
      *
      * 综上, 最后的结果只包含2和3(当然当总长度为2和3时单独处理),
      * 那么很显然n >= 5时， 3*(n - 3) >= 2 * (n - 2) ，因此我们优先拆成3，最后剩余的拆成2。最后的结果一定是由若干个3和1或2个2组成.
      *

     * create time: 2020-5-26 21:36
     * @params [n]
     * @return int
     */
    public int cuttingRope(int n) {
        if(n == 2) {
            return 1;
        }
        if(n == 3){
            return 2;
        }
        int mod = (int)1e9 + 7;
        long res = 1;
        while(n > 4) {
            res *= 3;
            res %= mod;
            n -= 3;
        }
        return (int)(res * n % mod);
    }
    public static void main(String[] args) {
        May26 m = new May26();
        int[] list = {31,26,33,21,40};
        m.lastStoneWeightII(list);
        System.out.println(m.waysToChange(26));
        System.out.println(m.numDecodings2("101"));
    }
}
